
import unittest
from collections import deque

class WinnerTree(object):

    '''
    'arrays' parameter contains arrays sorted in descending order
    '''
    def __init__(self, arrays):
        rootAndSize = self.__construct(arrays)
        self.__root = rootAndSize[0]
        self.__size = rootAndSize[1]
        pass

    '''
    Pop min element from tree.
    N - number of sorted sequences
    Time: O(lg N)
    Space: O(1)
    '''
    def popMin(self):

        if self.__size == 0:
            raise ValueError("Can't popMin() from empty WinnerTree")

        # TODO: implement this
        '''
        Two situations possible:
        1) current leaf isn't empty
        2) current leaf empty - remove this leaf node and it's parent, propagate element from right node if exists
        '''

        self.__size -= 1

    '''
    Get min element (aka root value), don't remove element from tree
    Time: O(1)
    Space: O(1)
    '''
    def getMin(self):
        return self.__root.getValue()

    def isEmpty(self):
        return self.__size == 0

    @property
    def size(self):
        return self.__size


    def __construct(self, arrays):
        base = deque()
        size = 0

        for array in arrays:
            base.append( Leaf(array) )
            size += len(array)

        while len(base) > 1:
            left = base.popleft()
            right = base.popleft()

            minValue = min( left.getValue(), right.getValue() )

            if minValue == right.getValue():
                left, right = right, left

            node = Node(minValue, left, right)
            left.parent = node
            right.parent = node

            base.append( node )

        return (base.popleft(), size)



class Leaf(object):

    def __init__(self, arr):
        self.index = 0
        self.arr = arr
        self.parent = None

    def getValue(self):
        return self.arr[self.index]

    def next(self):
        self.index += 1

    def hasNext(self):
        return self.index < len(self.arr)

    def isLeaf(self):
        return True

    def __str__(self):
        return str(self.arr)

    def __repr__(self):
        return str(self.arr)

class Node(object):

    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right
        self.parent = None

    def getValue(self):
        return self.value

    def __str__(self):
        return str(self.value)
    
    def __repr__(self):
        return str(self.value)

    def isLeaf(self):
        return False

    

class WinnerTreeTest(unittest.TestCase):

    def setUp(self):
        self.tree = WinnerTree( [[8, 19, 20], [22, 25, 30], [15, 20, 26], [45, 52, 62],
            [37, 40, 50], [41, 42, 43], [18, 21, 36], [26, 31, 38] ] )

    def testGetMin(self):
        self.assertFalse( self.tree.isEmpty() )
        self.assertEqual( 24, self.tree.size )

        self.assertEqual( 8, self.tree.getMin() )
        self.assertFalse( self.tree.isEmpty() )
        self.assertEqual( 24, self.tree.size )

        self.assertEqual( 8, self.tree.getMin() )
        self.assertFalse( self.tree.isEmpty() )
        self.assertEqual( 24, self.tree.size )

    def testPopMin(self):
        pass

        



if __name__ == "__main__":
    unittest.main(WinnerTreeTest)
  